The invention relates generally to the field of networking and network security, and specifically to improvements in the implementation of security arrangements that conform to the requirements of RFC 2401xe2x80x94xe2x80x9cSecurity Architecture for the Internet Protocolxe2x80x9d. Specifically, the invention uses a data structure and arrangement that groups dynamic rules into sets in which the rules in each group are order independent, thus allowing searching of such groups using enhanced non-sequential mechanisms, such as search trees.
RFC 2401 sets forth an architecture for the implementation of security in networks that use the IP protocol. This security architecture is commonly referred as IPsec. IPsec is the architecture endorsed by the Internet Engineering Task Force (IETF) for applying encryption and authentication security services to datagrams, or packets, at the IP layer of the protocol stack. The IPsec specification requires a Security Policy Database (SPD) that is used to determine how each incoming and outgoing packet is to be handled from a security perspective. The basic choices are deny packet, permit packet, and permit packet with Ipsec processing. If Ipsec processing is to be applied to a packet, the database specifies the precise processing that is to be applied. Because IPsec is applied at the IP layer, it is used for all upper layer protocols (TCP, UDP, ICMP, etc.) and it is applied as a connectionless protocol. That is, each IP packet is processed independently of any other packet.
In the known art, the SPD contains static rules and placeholders for dynamic rules. The rules and placeholders contain attributes to be matched against the corresponding attributes of incoming and outgoing packets to determine which rule should be applied to a packet. The attributes contained in the rules and placeholders might be different combinations of IP source address, source port, IP destination address, destination port and the protocol to be used. The attributes contained within a specific rule or placeholder can be as granular as specific hosts, ports and protocol for a match to occur, or as coarse as wild carded host pairs.
A static rule is essentially a policy rule. It is predefined for a network and generally not changed very often. For example, static rules might specify that all traffic between hosts A and B will be permitted without Ipsec processing and that all traffic between hosts A and C will be encrypted by IPsec. A dynamic rule is negotiated as needed and linked into the SPD database. The how, when and why of a dynamic rule negotiation is not part of the present invention and is not discussed in any detail. It suffices to say that when a dynamic rule is negotiated, the placeholder that contains the most specific attributes that includes the negotiated attributes is used to link the negotiated rule into the SPD database at the appropriate point. In the known art, the static rules, dynamic rules and placeholders are searched for every incoming and outgoing packet at a node to determine how to process the packet.
The IPsec architecture also requires that the rules be defined and processed in a specific order. This is absolutely necessary, because it is important for different hosts to apply the same type of security processing to the same packet. If a packet is encrypted with a specific algorithm, it is important that the receiving node locate the correct rule to decrypt the packet with the corresponding decryption algorithm. RFC 2401 requires that the SPD be ordered and that the SPD always be searched in the same order to insure consistent results at different nodes. The traditional technique of ordering the rules and placeholders in the SPD is from the most specific to least specific in terms of the specification of the attributes in the rules that are used for matching; the database (including static, dynamic rules and placeholders) is searched linearly in this order for every incoming and outgoing packet until a first match is found between the attributes of a packet and the attributes stored in a rule. At that point, the matching rule specifies whether the packet is denied, permitted without Ipsec processing or permitted with Ipsec processing. If the packet is permitted with Ipsec processing, the database specifies the details oft hat processing. This could be authentication or encryption or both.
In systems that become aggregation points (firewalls and servers) the number of filter rules in the database can be hundreds to thousands, depending on the network. In the known art, the SPD database is searched sequentially until a matching rule is found for all incoming and outgoing packets. This sequential search includes static rules and dynamic rules as they are encountered in the database. The performance cost on systems as a result of this searching is significant. In a system that has a mixture of IPsec and non-IPsec traffic, even the non-IPsec traffic is penalized because the filter rules must be searched to determine if a particular packet is subject to Ipsec processing or not.
The invention improves the performance of system IPsec rule searching in a number of ways. It is important that the Ipsec rules be searched in a predictable manner so that Ipsec processing applied at a sending end can be reversed at a receiving end. To achieve this predictability, Ipsec rules are searched in order from rules containing the most specificity of attributes to those containing the least specificity of attributes. In accordance with one aspect of the invention, the table of security rules is arranged in a way that significantly reduces the search time in most cases. The static rules include placeholders for sets of dynamic rules that are negotiated and entered into the dynamic sets as needed. The placeholders in the static table immediately precede and point to an associated set of dynamic rules. A set of dynamic rules is searched only if a match is found on the corresponding static placeholder during a search of the static rules. This dramatically improves performance, since most of the dynamic rules are not searched on a per packet basis, in contrast to the known prior art.
According to a second aspect of the invention, sets of dynamic rules are partitioned into separate groups such that within a group there is no rule order dependence. That is, within a group, the order of appearance of the rules is irrelevant. Because the rules for a group are order independent, each group can be represented by an enhanced search mechanism, rather than just a sequentially linked list of rules. Such mechanisms might be binary search trees, promoted lists and hash tables. A binary search tree, specifically a patricia tree, is used to represent each group in the preferred embodiment. There are five such groups in the preferred embodiment. The groups are searched in the order of groups containing the most specific attributes to those containing the least specific attributes. The attributes are source IP address (SA), destination IP address (DA), source port (SP), destination port (DP) and a protocol P. Each dynamic rule contained in the first group of dynamic rules specifies values for all five attributes (SA, DA, SP, DP, P). The second and third groups specify the IP addresses SA and DA and the protocol P. In addition, the second group specifies the source port SP; the third group specifies the destination port DP. The second and third groups are special in that which appears first in sequence is not important. The rules of the fourth group specify source address SA, destination address DA and the protocol attribute P. The rules of the fifth group specify only source address SA and destination address DA.
There is a sixth group which is order dependent and cannot be optimized for enhanced searching. The rules of the sixth group contain a range of addresses in either or both of the source and destination address fields. This fact makes the order of appearance of rules within the group important. The sixth group is searched by sequentially searching the rules themselves.
The searching of the security database is further improved by searching the database at layers higher than the IP layer as called for by RFC 2401 and as practiced by the known prior art. This allows the saving of security information associated with a matching rule to be saved in memory blocks associated with a connection, or in pseudo-connection memory blocks for packets not associated with a connection and using the stored information to avoid repeated searching of the database on every packet. In the preferred embodiment, this is done for the connection oriented TCP protocol and for the connectionless UDP protocol. In the disclosure herein, we shall refer to TCP and UDP protocols in reference to this feature of the invention. However, it should be understood that this is only the preferred embodiment and that this feature may be applied to other protocols as well.
Therefore, according to a third aspect of the invention, for connection oriented protocols such as TCP, binding information such as the Ipsec processing information from a matching rule or the address of a matching rule is stored in memory blocks associated with the connection. This allows the searching of the Ipsec rules to be performed generally only when a connection is first established. The matching rule or information from the matching rule is stored in the connection memory block and applied to each succeeding packet on the connection at the higher layer, without repeating a search of the security rules at the IP layer for every packet. If a static or dynamic rule is changed during the existence of a connection, a search of the rules must be repeated on the first packet after the rule change and a rebinding to the proper Ipsec rule made to insure proper Ipsec processing. In the preferred embodiment, a binding at the higher layer is done only to the static rule or to a static placeholder for a dynamic rule. This avoids the search of the static rules for packets after a connection has been established. However, the dynamic rules are searched for each packet arriving on a connection. The reason for this is that dynamic rules change much more often than static rules and it may not be efficient in practice to rebind on a connection for every dynamic rule change. In the preferred embodiment, a determination is made if a static rule or placeholder has changed by means of an instance count (IC) variable. When the static rule table is first initialized, the instance count (IC) is set to a non-zero value. Thereafter, every time the static table is changed, the value of IC is incremented. The value of IC is used at the higher layers to detect when static rule or placeholder has changed.
For connectionless protocols, each packet is independent of any prior packet. The attributes SA, DA, SP, DP and P may be completely different for each successive packet. Further, because there is no connection, there is no memory block associated with a connection into which Ipsec information can be saved.
Nevertheless, experience shows that for certain connectionless protocols like UDP, a significant number of consecutive packets tend to be associated with the same IP addresses and ports. Therefore, in accordance with a fourth feature of the invention, for selected connectionless protocols, packets are treated as if they were part of a connection-oriented protocol. A pseudo-connection memory block is allocated with the creation of each socket and Ipsec security binding information is stored in the pseudo-connection memory block on a first packet. Thereafter, as long as the source address and port in incoming packets on the same socket or destination address and port in outgoing packets on the socket remain the same, the packets are treated as part of a simulated connection. The security rules are not searched again until the simulated connection terminates or the static rule table is modified. In the preferred embodiment, only the repeated search of the static rules is omitted. The dynamic rules are searched for each packet.
This application is concerned primarily with the second aspect of the invention. The other aspects of the invention are the subject of separate applications. In the preferred embodiment of this invention, a database of security rules is searched for a match between the values of specified attributes of a packet and the values of corresponding attributes associated with each rule. The database is searched in the order of the rules containing the most specific values of attributes to the least specific values of attributes. The database is arranged into a set of relatively stable static rules and one or more sets of dynamic security rules. A static rule can be a placeholder for a set of dynamic rules. The static rules of the database are searched for the first static rule having attributes that match the corresponding attributes of the packet. Then it is determined if the matching static rule is a placeholder for a set of dynamic rules. If it is, the set of dynamic rules associated with the matching static rule is searched for a match between the packet attributes and attributes contained in the dynamic rules. The dynamic rules of a set are arranged in groups from groups having the most specific attributes to those having the least specific attributes. Within each group the rules are order independent. That is, within a group, the order of appearance of the rules does not matter. Each group is represented by a binary search tree which allows a quick and efficient search of a group. A sixth group of rules contains ranges of either or both of source and destination addresses. Because of this, the rules in the sixth are not order independent within the group and this group is searched sequentially.
In the preferred embodiment, the groups of dynamic rules are defined and searched in the following order:
a first group in which all attributes (source addressxe2x80x94SA, destination addressxe2x80x94DA, source portxe2x80x94SP, destination portxe2x80x94DP, and protocolxe2x80x94P) are specified,
a second group in which all attributes are specified except for one of the attributes SP or DP,
a third group in which all attributes are specified except for the attribute DP or SP that is specified in the second group,
a fourth group in which the attributes SA, DA and P are specified, and
a fifth group in which only the attributes SA and DA are specified.